Subdivision surfaces are emerging as a powerful representation for shape design. Their simplicity and potential to overcome difficulties associated with traditional spline-based modeling has made them a popular choice for several applications, including industrial modeling, movie production, and games.
Subdivision defines a smooth surface recursively, as the limit of a sequence of meshes. A finer mesh is obtained from a coarse mesh by applying a set of fixed refinement rules, for example the Catmull-Clark rules (see Catmull, E. and Clark, J., Recursively Generated B-Spline Surfaces on Arbitrary Topological Meshes, CAD 10(6), pp. 350-355, 1978). The initial, coarsest mesh is also known as the base mesh. FIG. 2 shows a prior art example of a base mesh and a sequence of refinements that lead to a smooth surface. A subdivision surface (FIG. 2E) is generated from an initial control polyhedron (FIG. 2A) by repeated subdivision (FIGS. 2B-2D). Control meshes obtained at several intermediate subdivision steps are shown in the middle (FIGS. 2B-2D). In this example, the Catmull-Clark subdivision scheme was applied.
The initial coarsest mesh serves as a base domain over which the resulting surface is naturally parameterized. See FIG. 3. Intuitively, the correspondence between control points on a given subdivision level and points in the base domain can be illustrated using two copies of the base mesh and applying in parallel midpoint subdivision on one copy (FIG. 3A) and Catmull-Clark subdivision on the other (FIG. 3B), as illustrated in FIG. 3. This ability to cast subdivision surfaces as parametric surfaces over a domain is crucial for many operations on this type of representation.
Some formal background on the definition and properties of natural parameterizations is now provided. A review of existing methods for exact evaluation at arbitrary parameter values is also included.
Throughout this disclosure, we use the term control point (or simply point) to refer to points computed by subdivision. We also use the term vertex to designate vertices of the polyhedron that serves as a base domain, as well as vertices added to it by midpoint subdivision. We also make use of the concepts of valence and extraordinary vertex/point. The valence of a vertex is an integer number equal to the number of faces incident to that vertex. A vertex is termed boundary vertex if it lies on the boundary of an open mesh. A vertex which is not a boundary vertex is called an interior vertex. For Catmull-Clark meshes, an interior vertex of the base mesh which has a valence different than four or a boundary vertex with valence different than two is deemed extraordinary (see vertex marked with circle 210 in FIG. 2A). The concepts of 1-ring and 2-ring around a vertex allow us to refer to the mesh neighborhood around that vertex. The 1-ring around a vertex is defined as the set of vertices belonging to faces adjacent to that vertex. The 2-ring around a vertex is defined as the set formed by the union of its 1-ring and the 1-rings of the vertices in the 1-ring different from the vertex itself. Parallel definitions can be obtained from the definitions above by replacing the word “vertex” with the word “point” to define the concepts of boundary point, interior point, extraordinary point, and 1-ring and 2-ring around a point.
More formally, let D denote the subset of R3 corresponding to the base domain. Repeated subdivision generates a sequence of piecewise linear maps defined over the common domain, D. When this sequence converges uniformly (as it is the case for the Catmull-Clark scheme), the limit map ƒ:D→R3 defines the limit surface of subdivision. For the Catmull-Clark scheme, the limit surface around an extraordinary point is completely defined by the set of points in the 2-ring around the extraordinary point. This set is called a control set. Let ƒ[p] denote the limit surface generated by subdivision from the control set p. For converging subdivision schemes, the limit function of subdivision can be decomposed into a sum of basis functions:
                                          f            ⁡                          [              p              ]                                ⁢                      (                          u              ,              v                        )                          =                              ∑            i                    ⁢                                    a              i                        ⁢                                          f                i                            ⁡                              (                                  u                  ,                  v                                )                                                                        (        1        )            
These so-called eigenbasis functions are the limit functions generated by the eigenvectors of the subdivision matrix S: ƒi:=ƒ[xi], where xi is the eigenvector of the subdivision matrix S corresponding to the eigenvalue λi: Sxi=λixi. It has been shown in Zorin, D. Subdivision and Multiresolution Surface Representations. Pd.D. Thesis, Caltech, 1997 that the eigenbasis functions satisfy the following scaling relation:
                                          f            i                    ⁡                      (                                          u                2                            ,                              v                2                                      )                          =                              λ            i                    ⁢                                    f              i                        ⁡                          (                              u                ,                v                            )                                                          (        2        )            
It is possible to directly evaluate subdivision surfaces and their derivatives up to any order at arbitrary parameter values without the need for explicit subdivision, as proposed in Stam, J., Exact Evaluation of Catmull-Clark Subdivision Surfaces at Arbitrary Parameter Values, Proceedings of Siggraph 98, pp. 395-404, 1998 and in Zorin, D. and Krisijansson, D., Evaluation of Piecewise Smooth Subdivision Surfaces, Visual Computer, 2002.
The evaluation algorithm described in Zorin, D. and Kristjansson, D., Evaluation of Piecewise Smooth Subdivision Surfaces, Visual Computer, 2002 is now reviewed in the context of the Catmull-Clark subdivision scheme.
The evaluation problem can be stated as follows: “Given a quadrilateral face j of the base mesh parameterized over the unit square [0,1]×[0,1] and parametric coordinates (u,v) within this face, find the value of the subdivision surface ƒ(u,v,j)εR3 at this parameter value.”
If the given quadrilateral face contains no extraordinary vertices, the surface can be evaluated as a bi-cubic spline patch defined by the control vertices of the face after an additional subdivision step. If the face contains extraordinary vertices, we can assume without restricting the generality of the problem, that it has a single extraordinary vertex (otherwise the problem can be reduced to this case after one subdivision step).
Let y=(u,v,j) be a point in the domain of the surface different from an extraordinary vertex. An important observation is that there exists a sufficiently fine subdivision level m such that y is located in a quadrilateral Q on level m and the control mesh of Q does not contain any extraordinary vertices. This means that the surface over Q is polynomial and can be evaluated explicitly (including at pointy) using bi-cubic spline evaluation. Obviously, for points closer to the extraordinary vertex, the level in is higher than for points farther away. This interpretation leads to a conceptual decomposition of the neighborhood around an extraordinary vertex into concentric layers. These layers correspond to the number of subdivision steps required to isolate the location being evaluated from the extraordinary vertex. Formally, if S denotes the subdivision matrix, the control meshes of quadrilaterals on level in can be computed from the initial control mesh by a multiplication with the m-th power of the subdivision matrix: S′″. These observations lead to a direct evaluation algorithm as outlined in the pseudo-code of Algorithm 1 and as illustrated in the flowchart of FIG. 5.